package basic_datastructure.linear;

/**
 * 数组的增加和删除操作实现
 * 时间复杂度：插入和删除的时间复杂度都为O(N)
 */
public class ArrayUpAndDel {
    /**
     * 定义成员变量
     */
    private int[] array;
    private int size;   //数组元素的个数

    //定义构造
    public ArrayUpAndDel(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }

    /**
     * @param index   插入的位置
     * @param element 插入的元素
     */
    public void Insert(int index, int element) throws Exception {
        //如果index>size 或者 index < 0 认为是非法输入
        //当插入元素的位置在数组尾部，index = size; 如果插入元素的位置在中间或头部index < size;
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际的元素范围");
        }

        //超范围插入 --> 扩容
        if (size >= array.length) {
            revise();
        }
        //从右向左循环，将元素逐个向右移动1位
        for (int i = size - 1; i >= index; i--) {
            array[i+1] = array[i];
        }
        //插入新元素
        array[index] = element;
        size++;
    }

    /**
     * 数组删除元素
     *
     * @param index 删除的位置
     * @return 返回被删除的元素
     */
    public int delete(int index) {
        //先判断越界
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }
        int deleteElement = array[index];
        //从删除的位置向右遍历,将元素逐个向左挪1位
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return deleteElement;
    }

    //遍历数组
    public void printArray() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /*
        扩容机制：不断插入后，元素个数将超过数组范围，此时进行扩容
        扩容原理：创建一个新数组，长度为原数组的2倍，将原数组复制到新数组中。
     */
    private void revise() {
        //创建一个新数组
        int[] newArray = new int[array.length * 2];
        //把旧数组元素复制到新数组
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }

    public static void main(String[] args) throws Exception {
        ArrayUpAndDel ai = new ArrayUpAndDel(4);
        ai.Insert(0, 3);
        ai.Insert(1, 2);
        ai.Insert(2, 9);
        ai.Insert(3, 5);
        ai.Insert(1, 6);
        ai.printArray();

    }
}
